The embodiments relate to a method and device for processing data, in particular for the cryptographic processing of data.
The technical field of the embodiments relate to the cryptographic processing of data based on elliptic curves.
Cryptographic methods are used inter alia for encrypting messages, signing documents and authenticating persons or objects. Particularly suitable for this purpose are so-called asymmetric encryption methods which provide a user both a private, secretly held key and a public key.
When encrypting a message the sender obtains the public key of the desired addressee and uses it to encrypt the message. Only the addressee is subsequently able to decrypt the message again using the private key that is known only to him/her.
When signing a document a signee calculates an electronic signature from a document by means of his/her private key. Other persons can verify the signature without difficulty with the aid of the signee's public key. However, only signatures that are signed using the associated private key can be verified by means of the public key. Based on this unique assignment and the assumption that the private key is kept secret by the signee, there results a unique assignment of the signature to the signee and the document.
When authenticating by means of a challenge-response protocol, a certification authority transmits a challenge to a person/object and requests the latter to calculate a response using the private key of the person/object and send back said response. A positive authentication results if the certification authority can verify the returned response using the public key of the person/object that is to be checked.
Asymmetric cryptography methods are based, as explained above, on a private and a public key. In such schemes the public key is generated from the private key by means of a predetermined algorithm. It is crucial for the cryptographic methods that a reversal of the process, i.e. determining the private key from the public key, cannot be accomplished within acceptable time limits using the available computing capacities. The latter is assured if the key length of the private key reaches a minimum length. The minimum length of the key is dependent on the algorithms used for the encryption and on the determination of the public key.
The operations using the public or private keys necessitate a certain amount of computing overhead. The latter is dependent on the algorithms used and also on the length of the keys used. It proves advantageous here to employ cryptographic methods based on elliptic curves, since these afford a high level of security with short key lengths. In contrast to other methods, for cryptography methods based on elliptic curves there is no known way to date of determining the private key from the public key where the computing overhead increases more slowly than with exponential increase with increasing key length. In other words, the security gain per additional bit length of the key used is higher than is the case with other methods. Much shorter key lengths can therefore be used for real-world applications.
An elliptic curve E is generally defined by means of a Weierstrass equation, which is written as the following cubic equation:y2+a1xy+a3y=x3+a2x2+a4x+a6.In this case a1 a2 a3 a4 a6 are permanently selected elements of a field K and the pairs (x, y) are called points of the elliptic curve E and satisfy the Weierstrass equation. A finite field K is chosen for the cryptographic methods. Accordingly, the number of points of the elliptic curve E is also finite and is designated in the following as order ord(E) of the curve E. In addition, a formal point at infinity is introduced.
An abelian group structure G can be defined on the set of points of the elliptic curve. The operation of the abelian group structure is designated below as addition and is written additively. The addition of any two points of the elliptic curve uniquely yields a third point of the elliptic curve. In this way it is also possible to define a scalar multiplication, which is defined as a multiple addition of a point to itself. Let P be a point on the elliptic curve E, s a whole number, and Q=sP the s-fold of the point P. Q is likewise a point on the elliptic curve. The determination of the scalar s for given points P and Q is referred to as the discrete logarithm problem for elliptic curves. Given a suitable choice of the field K and the parameters of the elliptic curve E it is impossible to solve the discrete logarithm problem within an acceptable time using currently available computer equipment. This difficulty forms the foundation for the security of cryptographic methods based on elliptic curves.
A communications user chooses a scalar s as his/her private key and keeps this secret. From a starting point P he/she also generates the public key Q as the scalar multiple of the starting point P with the scalar s. There is agreement between the communications users with regard to the starting point P. Owing to the high computational overhead of the discrete logarithm problem it is not possible to determine the private key s from the public key Q and consequently the security of cryptographic methods using elliptic curves is assured. A further requirement to be fulfilled by the elliptic curves is that their order is a large prime number or the product of a large prime number and a small number.
The cryptographic methods represent a compromise between an expected level of security and the computational overhead involved in the encrypting of data. In DE 10161138 A1 it is shown that it is possible to determine the scalar multiple of a point solely on the basis of the x-coordinate, without reference to the y-coordinate. Corresponding computing rules are described for arbitrary fields in DE 10161138 A1. By this means considerably more efficient implementations of the point arithmetic can be achieved, e.g. a Montgomery ladder for the scalar multiplication, a smaller number of field multiplications per point addition and a smaller number of registers for the point representation and the intermediate results. With this method it is not, however, checked as to whether a point is really an element of the elliptic curve.
From this there arises the possibility of carrying out an attack, whereby an x-coordinate of a point can be transmitted to an encryption device, wherein the point does not lie on the elliptic curve. In this regard it is described in DE 10161138 A1 that by this means a partial reconstruction of the private key of the encryption device is possible. To prevent such a side-channel attack, DE 10161138 A1 uses specially selected elliptic curves. The twisted elliptic curves associated with the elliptic curves serve as a criterion in this case. The associated twisted elliptic curve is defined as follows:y2+va1xy+a3y=x3+va2x2+v2a4x+v3a6,where the parameters a1, a2, a3, a4, a6 are the parameters of the elliptic curves. The parameter v is an arbitrary non-square of the field K if the characteristic of the field K is odd, or an element of the field K with track 1 if the characteristic is 2. According to DE 10161138 A1, all these twisted elliptic curves should also have an order which is a large prime number or the product of a large prime number and a small number.
In their article titled “The Static Diffie-Hellman Problem”, the authors Daniel R. L. Brown and Robert P. Gallant describe a further possibility for mounting an attack in order to find out a private key either fully or in part.
The attack on cryptographic methods whose security is based on the discrete logarithm problem in a finite group, as described in the publication “The Static Diffie-Hellman Problem”, is applicable in particular to elliptic curves. The attack described can be carried out particularly efficiently when an attacker has at his disposal a device, conventionally called an oracle in the literature, which contains a secret scalar s and when an arbitrary point U is input returns the result of the calculation T=sU, hence the result point T of the scalar multiplication, to the attacker. With this attack, in particular a sequence of points P0, P1, P2, . . . , Pn on the elliptic curve is required, where Pi=sPi-1,P0=P applies.
In a conventional elliptic-curve-based authentication protocol that is known internally to the applicant, a scalar multiplication is computed. The x-coordinate in a randomly chosen projective representation (X2, Z2) is returned as the result of said scalar multiplication. Compared to the static Diffie-Hellman attack, the security of the authentication protocol is conventionally based on the properties of the elliptic curve used.